
#ifndef AFTERMATH_ALGEBRA_FACTORIZATION_HPP_INCLUDED
#define AFTERMATH_ALGEBRA_FACTORIZATION_HPP_INCLUDED

#include <initializer_list>

namespace aftermath
{
    namespace algebra
    {
        struct factorization
        {
            template <typename T>
            static T greatest_common_divisor(T a, T b)
            {
                if (a == 0) return b;
                if (b == 0) return a;

                if (a > b) return factorization::greatest_common_divisor(a - b * (a / b), b);
                if (b > a) return factorization::greatest_common_divisor(a, b - a * (b / a));
                return a;
            }

            template <typename T>
            static T greatest_common_divisor(std::initializer_list<T> a)
            {
                std::size_t n = a.size();
                if (n == 0U) return 1;
                auto it = a.begin();
                T result = *it;
                ++it;
                for (; it != a.end(); ++it) result = factorization::greatest_common_divisor(result, *it);
                return result;
            }

            template <typename T>
            static T least_common_multiplier(T a, T b)
            {
                return a > b ?
                    ((a / factorization::greatest_common_divisor(a, b)) * b) :
                    ((b / factorization::greatest_common_divisor(a, b)) * a);
            }

            template <typename T>
            static T least_common_multiplier(std::initializer_list<T> a)
            {
                std::size_t n = a.size();
                if (n == 0U) return 1;
                auto it = a.begin();
                T result = *it;
                ++it;
                for (; it != a.end(); ++it) result = factorization::least_common_multiplier(result, *it);
                return result;
            }
        };
    }
}

#endif // AFTERMATH_ALGEBRA_FACTORIZATION_HPP_INCLUDED
